//https://leetcode.cn/problems/sum-of-subarray-minimums/description/?envType=daily-question&envId=2023-11-27




class Solution {
public:
    const int MOD=1e9+7;
    int sumSubarrayMins(vector<int>& arr) {
        int n=arr.size();
        vector<int> leftpos(n,-1),rightpos(n,n);
        for(int i=n-2,j=n-1;i>=0;j=i--){
            while(j<n&&arr[j]>arr[i])j=rightpos[j];
            rightpos[i]=j;
        }
        long long res=1LL*arr[0]*rightpos[0]%MOD;
        for(int i=1,j=0;i<n;j=i++){
            while(j>=0&&arr[j]>=arr[i])j=leftpos[j];
            leftpos[i]=j;
            res=(res+1LL*arr[i]*(i-j)*(rightpos[i]-i))%MOD;
        }
        return res;
    }
};